

/*-------------------------------------------------------------------------
 *
 * dshash.c
 *	  基于动态共享内存区域的并发哈希表。
 *
 * 这是一个开放哈希表，每个表项都有一个链表。它支持动态调整大小，以防止链表在平均情况下生长得过长。目前，只支持扩展：哈希表永远不会缩小。
 *
 * 为了处理并发，它有一个固定大小的分区集合，每个分区都是独立锁定的。每个桶映射到一个分区；因此插入、查找和迭代操作通常只获取一个锁。因此，只要这些操作在锁分区级别不发生冲突，就能实现良好的并发。但是，当调整大小操作开始时，所有分区锁必须在短时间内同时获取。这种情况预计只会发生少数几次，直到找到稳定的大小，因为增长是几何级数的。
 *
 * 将来的版本可能支持迭代器和增量调整大小；目前的实现是极简的。
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *	  src/backend/lib/dshash.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "common/hashfn.h"
#include "lib/dshash.h"
#include "storage/ipc.h"
#include "storage/lwlock.h"
#include "utils/dsa.h"
#include "utils/memutils.h"

/*
 * 哈希表中的一个项。这将用户的条目对象包装在一个
 * 包装中，持有一个指向桶的指针和一个指向桶中下一个
 * 项的指针。
 */
struct dshash_table_item
{
	/* 同一桶中的下一个项。 */
	dsa_pointer next;
	/* 哈希键，以避免重新计算。 */
	dshash_hash hash;
	/* 用户的条目对象在此之后。请参见 ENTRY_FROM_ITEM(item)。 */
};

/*
 * 用于锁定目的的分区数量。目前设置为与
 * NUM_BUFFER_PARTITIONS 匹配，基于对缓冲池足够的内容
 * 对于任何其他目的也必须足够的假设。将来这可能成为
 * 运行时参数。
 */
#define DSHASH_NUM_PARTITIONS_LOG2 7
#define DSHASH_NUM_PARTITIONS (1 << DSHASH_NUM_PARTITIONS_LOG2)

/* 用于识别我们哈希表的魔法值。 */
#define DSHASH_MAGIC 0x75ff6a20

/*
 * 每个锁定分区的跟踪信息。最初，每个分区
 * 对应一个桶，但是每次哈希表增长时，每个分区覆盖的桶
 * 将分裂，因此所覆盖的桶数量加倍。
 *
 * 我们可能想在这里添加填充，以便每个分区位于不同的
 * 缓存行，但这样做将显著膨胀这个结构。
 */
typedef struct dshash_partition
{
	LWLock		lock;			/* 保护此分区中的所有桶。 */
	size_t		count;			/* 此分区桶中的项数 */
} dshash_partition;

/*
 * 哈希表的头对象。将存储在动态共享
 * 内存中。
 */
typedef struct dshash_table_control
{
	dshash_table_handle handle;
	uint32		magic;
	dshash_partition partitions[DSHASH_NUM_PARTITIONS];
	int			lwlock_tranche_id;

	/*
	 * 只有在持有所有分区锁的情况下才能写入以下成员。
	 * 当持有任何一个分区锁时可以进行读取。
	 */

	/* 以 2 的幂表示的桶数量（8 = 256 桶）。 */
	size_t		size_log2;		/* log2(桶数量) */
	dsa_pointer buckets;		/* 当前桶数组 */
} dshash_table_control;

/*
 * 动态哈希表的每个后端状态。
 */
struct dshash_table
{
	dsa_area   *area;			/* 支持动态共享内存区域。 */
	dshash_parameters params;	/* 参数。 */
	void	   *arg;			/* 用户提供的数据指针。 */
	dshash_table_control *control;	/* DSM 中的控制对象。 */
	dsa_pointer *buckets;		/* DSM 中的当前桶指针。 */
	size_t		size_log2;		/* log2(桶数量) */
};

/* 给定一个指向项的指针，找到它所持有的条目（用户数据）。 */
#define ENTRY_FROM_ITEM(item) \
	((char *)(item) + MAXALIGN(sizeof(dshash_table_item)))

/* 给定一个指向条目的指针，找到持有它的项。 */
#define ITEM_FROM_ENTRY(entry)											\
	((dshash_table_item *)((char *)(entry) -							\
							 MAXALIGN(sizeof(dshash_table_item))))

/* 进行了多少次调整大小操作（桶分裂）？ */
#define NUM_SPLITS(size_log2)					\
	(size_log2 - DSHASH_NUM_PARTITIONS_LOG2)

/* 给定大小中有多少个桶？ */
#define NUM_BUCKETS(size_log2)		\
	(((size_t) 1) << (size_log2))

/* 给定大小中每个分区中有多少个桶？ */
#define BUCKETS_PER_PARTITION(size_log2)		\
	(((size_t) 1) << NUM_SPLITS(size_log2))

/* 在我们需要增长之前的最大条目。半 + 四分之一 = 75% 负载因子。 */
#define MAX_COUNT_PER_PARTITION(hash_table)				\
	(BUCKETS_PER_PARTITION(hash_table->size_log2) / 2 + \
	 BUCKETS_PER_PARTITION(hash_table->size_log2) / 4)

/* 基于哈希的高位选择分区。 */
#define PARTITION_FOR_HASH(hash)										\
	(hash >> ((sizeof(dshash_hash) * CHAR_BIT) - DSHASH_NUM_PARTITIONS_LOG2))

/*
 * 找到给定哈希和表大小的桶索引。每次表
 * 大小加倍时，给定哈希值的适当桶加倍并
 * 可能加一，具体取决于新显露的位，以便所有桶
 * 被分裂。
 */
#define BUCKET_INDEX_FOR_HASH_AND_SIZE(hash, size_log2)		\
	(hash >> ((sizeof(dshash_hash) * CHAR_BIT) - (size_log2)))

/* 给定分区中第一个桶的索引。 */
#define BUCKET_INDEX_FOR_PARTITION(partition, size_log2)	\
	((partition) << NUM_SPLITS(size_log2))

/* 基于桶索引选择分区。 */
#define PARTITION_FOR_BUCKET_INDEX(bucket_idx, size_log2)				\
	((bucket_idx) >> NUM_SPLITS(size_log2))

/* 给定哈希值的活动桶的头部（左值）。 */
#define BUCKET_FOR_HASH(hash_table, hash)								\
	(hash_table->buckets[												\
		BUCKET_INDEX_FOR_HASH_AND_SIZE(hash,							\
									   hash_table->size_log2)])

static void fc_delete_item(dshash_table *fc_hash_table,
						dshash_table_item *fc_item);
static void fc_resize(dshash_table *fc_hash_table, size_t fc_new_size);
static inline void fc_ensure_valid_bucket_pointers(dshash_table *fc_hash_table);
static inline dshash_table_item *fc_find_in_bucket(dshash_table *fc_hash_table,
												const void *fc_key,
												dsa_pointer fc_item_pointer);
static void fc_insert_item_into_bucket(dshash_table *fc_hash_table,
									dsa_pointer fc_item_pointer,
									dshash_table_item *fc_item,
									dsa_pointer *fc_bucket);
static dshash_table_item *fc_insert_into_bucket(dshash_table *fc_hash_table,
											 const void *fc_key,
											 dsa_pointer *fc_bucket);
static bool fc_delete_key_from_bucket(dshash_table *fc_hash_table,
								   const void *fc_key,
								   dsa_pointer *fc_bucket_head);
static bool fc_delete_item_from_bucket(dshash_table *fc_hash_table,
									dshash_table_item *fc_item,
									dsa_pointer *fc_bucket_head);
static inline dshash_hash fc_hash_key(dshash_table *fc_hash_table, const void *fc_key);
static inline bool fc_equal_keys(dshash_table *fc_hash_table,
							  const void *fc_a, const void *fc_b);

#define PARTITION_LOCK(hash_table, i)			\
	(&(hash_table)->control->partitions[(i)].lock)

#define ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(hash_table) \
	Assert(!LWLockAnyHeldByMe(&(hash_table)->control->partitions[0].lock, \
		   DSHASH_NUM_PARTITIONS, sizeof(dshash_partition)))

/*
 * 创建一个新的哈希表，基于给定的动态共享区域，使用给定的参数。返回的对象在后端本地内存中分配，使用当前的 MemoryContext。'arg' 将传递给比较和哈希函数。
 */
dshash_table *
dshash_create(dsa_area *fc_area, const dshash_parameters *fc_params, void *fc_arg)
{
	dshash_table *fc_hash_table;
	dsa_pointer fc_control;

	/* 分配代表哈希表的后端本地对象。 */
	fc_hash_table = palloc(sizeof(dshash_table));

	/* 在共享内存中分配控制对象。 */
	fc_control = dsa_allocate(fc_area, sizeof(dshash_table_control));

	/* 设置本地和共享哈希表结构。 */
	fc_hash_table->area = fc_area;
	fc_hash_table->params = *fc_params;
	fc_hash_table->arg = fc_arg;
	fc_hash_table->control = dsa_get_address(fc_area, fc_control);
	fc_hash_table->control->handle = fc_control;
	fc_hash_table->control->magic = DSHASH_MAGIC;
	fc_hash_table->control->lwlock_tranche_id = fc_params->tranche_id;

	/* 设置锁分区的数组。 */
	{
		dshash_partition *fc_partitions = fc_hash_table->control->partitions;
		int			fc_tranche_id = fc_hash_table->control->lwlock_tranche_id;
		int			fc_i;

		for (fc_i = 0; fc_i < DSHASH_NUM_PARTITIONS; ++fc_i)
		{
			LWLockInitialize(&fc_partitions[fc_i].lock, fc_tranche_id);
			fc_partitions[fc_i].count = 0;
		}
	}

	/*
	 * 设置初始桶数组。我们的初始大小与分区数量相同。
	 */
	fc_hash_table->control->size_log2 = DSHASH_NUM_PARTITIONS_LOG2;
	fc_hash_table->control->buckets =
		dsa_allocate_extended(fc_area,
							  sizeof(dsa_pointer) * DSHASH_NUM_PARTITIONS,
							  DSA_ALLOC_NO_OOM | DSA_ALLOC_ZERO);
	if (!DsaPointerIsValid(fc_hash_table->control->buckets))
	{
		dsa_free(fc_area, fc_control);
		ereport(ERROR,
				(errcode(ERRCODE_OUT_OF_MEMORY),
				 errmsg("out of memory"),
				 errdetail("Failed on DSA request of size %zu.",
						   sizeof(dsa_pointer) * DSHASH_NUM_PARTITIONS)));
	}
	fc_hash_table->buckets = dsa_get_address(fc_area,
										  fc_hash_table->control->buckets);
	fc_hash_table->size_log2 = fc_hash_table->control->size_log2;

	return fc_hash_table;
}

/*
 * 使用句柄附加到现有哈希表。返回的对象在后端本地内存中分配，使用当前的 MemoryContext。'arg' 将传递给比较和哈希函数。
 */
dshash_table *
dshash_attach(dsa_area *fc_area, const dshash_parameters *fc_params,
			  dshash_table_handle fc_handle, void *fc_arg)
{
	dshash_table *fc_hash_table;
	dsa_pointer fc_control;

	/* 分配代表哈希表的后端本地对象。 */
	fc_hash_table = palloc(sizeof(dshash_table));

	/* 在共享内存中查找控制对象。 */
	fc_control = fc_handle;

	/* 设置本地哈希表结构。 */
	fc_hash_table->area = fc_area;
	fc_hash_table->params = *fc_params;
	fc_hash_table->arg = fc_arg;
	fc_hash_table->control = dsa_get_address(fc_area, fc_control);
	Assert(fc_hash_table->control->magic == DSHASH_MAGIC);

	/*
	 * 这些稍后将由 ensure_valid_bucket_pointers() 设置为正确的值，
	 * 此时我们将持有一个分区锁，以防止并发调整大小。
	 */
	fc_hash_table->buckets = NULL;
	fc_hash_table->size_log2 = 0;

	return fc_hash_table;
}

/*
 * 从哈希表分离。这会释放与哈希表相关联的后端本地资源，但哈希表将继续存在，直到被显式销毁（由仍附加到它的后端），或者支撑它的区域返回给操作系统。
 */
void dshash_detach(dshash_table *fc_hash_table)
{
	ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(fc_hash_table);

	/* 哈希表可能已被销毁。只需释放本地内存。 */
	pfree(fc_hash_table);
}

/*
 * 销毁哈希表，将所有内存返回给该区域。调用者必须确定在调用此函数之前，没有其他后端会尝试访问哈希表。其他后端必须显式调用 dshash_detach 来释放与哈希表相关联的后端本地内存。调用 dshash_destroy 的后端不得调用 dshash_detach。
 */
void dshash_destroy(dshash_table *fc_hash_table)
{
	size_t		fc_size;
	size_t		fc_i;

	Assert(fc_hash_table->control->magic == DSHASH_MAGIC);
	fc_ensure_valid_bucket_pointers(fc_hash_table);

	/* 释放所有条目。 */
	fc_size = NUM_BUCKETS(fc_hash_table->size_log2);
	for (fc_i = 0; fc_i < fc_size; ++fc_i)
	{
		dsa_pointer fc_item_pointer = fc_hash_table->buckets[fc_i];

		while (DsaPointerIsValid(fc_item_pointer))
		{
			dshash_table_item *fc_item;
			dsa_pointer fc_next_item_pointer;

			fc_item = dsa_get_address(fc_hash_table->area, fc_item_pointer);
			fc_next_item_pointer = fc_item->next;
			dsa_free(fc_hash_table->area, fc_item_pointer);
			fc_item_pointer = fc_next_item_pointer;
		}
	}

	/*
	 * 损坏控制块以帮助捕捉编程错误，以防其他后端访问以前由此哈希表占用的内存。
	 */
	fc_hash_table->control->magic = 0;

	/* 释放活动表和控制对象。 */
	dsa_free(fc_hash_table->area, fc_hash_table->control->buckets);
	dsa_free(fc_hash_table->area, fc_hash_table->control->handle);

	pfree(fc_hash_table);
}

/*
 * 获取一个句柄，供其他进程使用，以附加到此哈希表。
 */
dshash_table_handle
dshash_get_hash_table_handle(dshash_table *fc_hash_table)
{
	Assert(fc_hash_table->control->magic == DSHASH_MAGIC);

	return fc_hash_table->control->handle;
}

/*
 * 根据给定的键查找条目。如果找到具有给定键的条目，返回指向该条目的指针。如果未找到该键，则返回NULL。如果返回了非NULL值，则条目被锁定，必须通过调用dshash_release_lock来释放。如果在调用dshash_release_lock之前引发错误，锁将自动释放，但调用者必须注意确保条目不会被损坏。锁模式根据'exclusive'决定是共享的还是独占的。
 *
 * 调用者不得已经持有锁。
 *
 * 注意，持有的锁实际上是LWLock，因此在从此函数返回时将保持中断，直到调用dshash_release_lock才会恢复。调用者应尽快释放锁是一个很好的主意。
 */
void * dshash_find(dshash_table *fc_hash_table, const void *fc_key, bool fc_exclusive)
{
	dshash_hash fc_hash;
	size_t		fc_partition;
	dshash_table_item *fc_item;

	fc_hash = fc_hash_key(fc_hash_table, fc_key);
	fc_partition = PARTITION_FOR_HASH(fc_hash);

	Assert(fc_hash_table->control->magic == DSHASH_MAGIC);
	ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(fc_hash_table);

	LWLockAcquire(PARTITION_LOCK(fc_hash_table, fc_partition),
				  fc_exclusive ? LW_EXCLUSIVE : LW_SHARED);
	fc_ensure_valid_bucket_pointers(fc_hash_table);

	/* 搜索活动桶。 */
	fc_item = fc_find_in_bucket(fc_hash_table, fc_key, BUCKET_FOR_HASH(fc_hash_table, fc_hash));

	if (!fc_item)
	{
		/* 未找到。 */
		LWLockRelease(PARTITION_LOCK(fc_hash_table, fc_partition));
		return NULL;
	}
	else
	{
		/* 调用者将通过调用dshash_release_lock释放锁。 */
		return ENTRY_FROM_ITEM(fc_item);
	}
}

/*
 * 返回指向独占锁定项的指针，该项必须使用dshash_release_lock释放。如果在哈希表中找到该键，则'found'被设置为true，并返回指向现有条目的指针。如果未找到该键，则'found'被设置为false，并返回指向新创建条目的指针。
 *
 * 上述关于dshash_find()的锁定和错误处理的注意事项同样适用于这里。
 */
void * dshash_find_or_insert(dshash_table *fc_hash_table,
					  const void *fc_key,
					  bool *fc_found)
{
	dshash_hash fc_hash;
	size_t		fc_partition_index;
	dshash_partition *fc_partition;
	dshash_table_item *fc_item;

	fc_hash = fc_hash_key(fc_hash_table, fc_key);
	fc_partition_index = PARTITION_FOR_HASH(fc_hash);
	fc_partition = &fc_hash_table->control->partitions[fc_partition_index];

	Assert(fc_hash_table->control->magic == DSHASH_MAGIC);
	ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(fc_hash_table);

restart:
	LWLockAcquire(PARTITION_LOCK(fc_hash_table, fc_partition_index),
				  LW_EXCLUSIVE);
	fc_ensure_valid_bucket_pointers(fc_hash_table);

	/* 搜索活动桶。 */
	fc_item = fc_find_in_bucket(fc_hash_table, fc_key, BUCKET_FOR_HASH(fc_hash_table, fc_hash));

	if (fc_item)
		*fc_found = true;
	else
	{
		*fc_found = false;

		/* 检查我们是否变得太满。 */
		if (fc_partition->count > MAX_COUNT_PER_PARTITION(fc_hash_table))
		{
			/*
			 * 由此分区保护的所有桶的负载因子（= keys / buckets）> 0.75。假设整个哈希表一般也适用这一点（尽管我们不试图直接跟踪以避免在某种中央计数器上的争用；我们只是假设这个分区是具有代表性的）。现在是调整大小的好时机。
			 *
			 * 首先放弃我们现有的锁，因为调整大小需要以正确的顺序重新获取所有的锁以避免死锁。
			 */
			LWLockRelease(PARTITION_LOCK(fc_hash_table, fc_partition_index));
			fc_resize(fc_hash_table, fc_hash_table->size_log2 + 1);

			goto restart;
		}

		/* 最后我们可以尝试插入新项。 */
		fc_item = fc_insert_into_bucket(fc_hash_table, fc_key,
								  &BUCKET_FOR_HASH(fc_hash_table, fc_hash));
		fc_item->hash = fc_hash;
		/* 调整每个锁分区的计数器以获取负载因子的知识。 */
		++fc_partition->count;
	}

	/* 调用者必须使用dshash_release_lock释放锁。 */
	return ENTRY_FROM_ITEM(fc_item);
}

/*
 * 通过键删除条目。如果找到该键并删除了相应的条目，返回true。
 *
 * 要删除您已经有指针的条目，请参见dshash_delete_entry。
 */
bool dshash_delete_key(dshash_table *fc_hash_table, const void *fc_key)
{
	dshash_hash fc_hash;
	size_t		fc_partition;
	bool		fc_found;

	Assert(fc_hash_table->control->magic == DSHASH_MAGIC);
	ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(fc_hash_table);

	fc_hash = fc_hash_key(fc_hash_table, fc_key);
	fc_partition = PARTITION_FOR_HASH(fc_hash);

	LWLockAcquire(PARTITION_LOCK(fc_hash_table, fc_partition), LW_EXCLUSIVE);
	fc_ensure_valid_bucket_pointers(fc_hash_table);

	if (fc_delete_key_from_bucket(fc_hash_table, fc_key,
							   &BUCKET_FOR_HASH(fc_hash_table, fc_hash)))
	{
		Assert(fc_hash_table->control->partitions[fc_partition].count > 0);
		fc_found = true;
		--fc_hash_table->control->partitions[fc_partition].count;
	}
	else
		fc_found = false;

	LWLockRelease(PARTITION_LOCK(fc_hash_table, fc_partition));

	return fc_found;
}

/*
 * 删除条目。条目必须已经被独占锁定，并且必须通过dshash_find或dshash_find_or_insert获得。注意，此函数释放锁就像dshash_release_lock一样。
 *
 * 要通过键删除条目，请参见dshash_delete_key。
 */
void dshash_delete_entry(dshash_table *fc_hash_table, void *fc_entry)
{
	dshash_table_item *fc_item = ITEM_FROM_ENTRY(fc_entry);
	size_t		fc_partition = PARTITION_FOR_HASH(fc_item->hash);

	Assert(fc_hash_table->control->magic == DSHASH_MAGIC);
	Assert(LWLockHeldByMeInMode(PARTITION_LOCK(fc_hash_table, fc_partition),
								LW_EXCLUSIVE));

	fc_delete_item(fc_hash_table, fc_item);
	LWLockRelease(PARTITION_LOCK(fc_hash_table, fc_partition));
}

/*
 * 解锁由dshash_find或dshash_find_or_insert锁定的条目。
 */
void dshash_release_lock(dshash_table *fc_hash_table, void *fc_entry)
{
	dshash_table_item *fc_item = ITEM_FROM_ENTRY(fc_entry);
	size_t		fc_partition_index = PARTITION_FOR_HASH(fc_item->hash);

	Assert(fc_hash_table->control->magic == DSHASH_MAGIC);

	LWLockRelease(PARTITION_LOCK(fc_hash_table, fc_partition_index));
}

/*
 * 一个转发到memcmp的比较函数。
 */
int dshash_memcmp(const void *fc_a, const void *fc_b, size_t fc_size, void *fc_arg)
{
	return memcmp(fc_a, fc_b, fc_size);
}

/*
 * 一个转发到tag_hash的哈希函数。
 */
dshash_hash
dshash_memhash(const void *fc_v, size_t fc_size, void *fc_arg)
{
	return tag_hash(fc_v, fc_size);
}

/*
 * 顺序扫描dshash表并逐个返回所有元素，当所有元素都已返回时返回NULL。
 *
 * 当扫描结束时需要调用dshash_seq_term。调用者可以在扫描过程中使用dshash_delete_current()删除已返回的元素（如果exclusive = true）。
 */
void dshash_seq_init(dshash_seq_status *fc_status, dshash_table *fc_hash_table,
				bool fc_exclusive)
{
	fc_status->hash_table = fc_hash_table;
	fc_status->curbucket = 0;
	fc_status->nbuckets = 0;
	fc_status->curitem = NULL;
	fc_status->pnextitem = InvalidDsaPointer;
	fc_status->curpartition = -1;
	fc_status->exclusive = fc_exclusive;
}

/*
 * 返回下一个元素。
 *
 * 返回的元素被锁定，调用者不能释放锁。锁将在未来对dshash_seq_next()或dshash_seq_term()的调用中释放。
 */
void * dshash_seq_next(dshash_seq_status *fc_status)
{
	dsa_pointer fc_next_item_pointer;

	/*
	 * 还没有持有任何分区锁。需要确定哈希表的大小，它可能在我们上次查看后进行了调整。
	 * 由于我们按分区顺序迭代，可以从无条件锁定分区0开始。
	 *
	 * 一旦我们持有锁，直到扫描结束之前无法进行调整。因此
	 * 我们不需要重复调用ensure_valid_bucket_pointers()。
	 */
	if (fc_status->curpartition == -1)
	{
		Assert(fc_status->curbucket == 0);
		ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(fc_status->hash_table);

		fc_status->curpartition = 0;

		LWLockAcquire(PARTITION_LOCK(fc_status->hash_table,
									 fc_status->curpartition),
					  fc_status->exclusive ? LW_EXCLUSIVE : LW_SHARED);

		fc_ensure_valid_bucket_pointers(fc_status->hash_table);

		fc_status->nbuckets =
			NUM_BUCKETS(fc_status->hash_table->control->size_log2);
		fc_next_item_pointer = fc_status->hash_table->buckets[fc_status->curbucket];
	}
	else
		fc_next_item_pointer = fc_status->pnextitem;

	Assert(LWLockHeldByMeInMode(PARTITION_LOCK(fc_status->hash_table,
											   fc_status->curpartition),
								fc_status->exclusive ? LW_EXCLUSIVE : LW_SHARED));

	/* 如果当前桶已完成，则移动到下一个桶 */
	while (!DsaPointerIsValid(fc_next_item_pointer))
	{
		int			fc_next_partition;

		if (++fc_status->curbucket >= fc_status->nbuckets)
		{
			/* 所有桶都已被扫描。结束。 */
			return NULL;
		}

		/* 检查是否移动到下一个分区 */
		fc_next_partition =
			PARTITION_FOR_BUCKET_INDEX(fc_status->curbucket,
									   fc_status->hash_table->size_log2);

		if (fc_status->curpartition != fc_next_partition)
		{
			/*
			 * 移动到下一个分区。锁定下一个分区然后
			 * 释放当前分区的锁，不要按反向顺序以避免
			 * 并发调整。通过以与resize()相同的顺序获取锁来避免死锁。
			 */
			LWLockAcquire(PARTITION_LOCK(fc_status->hash_table,
										 fc_next_partition),
						  fc_status->exclusive ? LW_EXCLUSIVE : LW_SHARED);
			LWLockRelease(PARTITION_LOCK(fc_status->hash_table,
										 fc_status->curpartition));
			fc_status->curpartition = fc_next_partition;
		}

		fc_next_item_pointer = fc_status->hash_table->buckets[fc_status->curbucket];
	}

	fc_status->curitem =
		dsa_get_address(fc_status->hash_table->area, fc_next_item_pointer);

	/*
	 * 调用者可以删除该项。存储下一个项以防删除。
	 */
	fc_status->pnextitem = fc_status->curitem->next;

	return ENTRY_FROM_ITEM(fc_status->curitem);
}

/*
 * 终止seqscan并释放所有锁。
 *
 * 需要在完成或退出seqscan时调用。
 */
void dshash_seq_term(dshash_seq_status *fc_status)
{
	if (fc_status->curpartition >= 0)
		LWLockRelease(PARTITION_LOCK(fc_status->hash_table, fc_status->curpartition));
}

/*
 * 删除seq扫描的当前条目。
 */
void dshash_delete_current(dshash_seq_status *fc_status)
{
	dshash_table *fc_hash_table = fc_status->hash_table;
	dshash_table_item *fc_item = fc_status->curitem;
	size_t		fc_partition PG_USED_FOR_ASSERTS_ONLY;

	fc_partition = PARTITION_FOR_HASH(fc_item->hash);

	Assert(fc_status->exclusive);
	Assert(fc_hash_table->control->magic == DSHASH_MAGIC);
	Assert(LWLockHeldByMeInMode(PARTITION_LOCK(fc_hash_table, fc_partition),
								LW_EXCLUSIVE));

	fc_delete_item(fc_hash_table, fc_item);
}

/*
 * 打印关于哈希表内部状态的调试信息到stderr。调用者必须不持有任何分区锁。
 */
void dshash_dump(dshash_table *fc_hash_table)
{
	size_t		fc_i;
	size_t		fc_j;

	Assert(fc_hash_table->control->magic == DSHASH_MAGIC);
	ASSERT_NO_PARTITION_LOCKS_HELD_BY_ME(fc_hash_table);

	for (fc_i = 0; fc_i < DSHASH_NUM_PARTITIONS; ++fc_i)
	{
		Assert(!LWLockHeldByMe(PARTITION_LOCK(fc_hash_table, fc_i)));
		LWLockAcquire(PARTITION_LOCK(fc_hash_table, fc_i), LW_SHARED);
	}

	fc_ensure_valid_bucket_pointers(fc_hash_table);

	fprintf(stderr,
			"hash table size = %zu\n", (size_t) 1 << fc_hash_table->size_log2);
	for (fc_i = 0; fc_i < DSHASH_NUM_PARTITIONS; ++fc_i)
	{
		dshash_partition *fc_partition = &fc_hash_table->control->partitions[fc_i];
		size_t		fc_begin = BUCKET_INDEX_FOR_PARTITION(fc_i, fc_hash_table->size_log2);
		size_t		fc_end = BUCKET_INDEX_FOR_PARTITION(fc_i + 1, fc_hash_table->size_log2);

		fprintf(stderr, "  partition %zu\n", fc_i);
		fprintf(stderr,
				"    active buckets (key count = %zu)\n", fc_partition->count);

		for (fc_j = fc_begin; fc_j < fc_end; ++fc_j)
		{
			size_t		fc_count = 0;
			dsa_pointer fc_bucket = fc_hash_table->buckets[fc_j];

			while (DsaPointerIsValid(fc_bucket))
			{
				dshash_table_item *fc_item;

				fc_item = dsa_get_address(fc_hash_table->area, fc_bucket);

				fc_bucket = fc_item->next;
				++fc_count;
			}
			fprintf(stderr, "      bucket %zu (key count = %zu)\n", fc_j, fc_count);
		}
	}

	for (fc_i = 0; fc_i < DSHASH_NUM_PARTITIONS; ++fc_i)
		LWLockRelease(PARTITION_LOCK(fc_hash_table, fc_i));
}

/*
 * 删除我们有指针的被锁定项。
 */
static void fc_delete_item(dshash_table *fc_hash_table, dshash_table_item *fc_item)
{
	size_t		fc_hash = fc_item->hash;
	size_t		fc_partition = PARTITION_FOR_HASH(fc_hash);

	Assert(LWLockHeldByMe(PARTITION_LOCK(fc_hash_table, fc_partition)));

	if (fc_delete_item_from_bucket(fc_hash_table, fc_item,
								&BUCKET_FOR_HASH(fc_hash_table, fc_hash)))
	{
		Assert(fc_hash_table->control->partitions[fc_partition].count > 0);
		--fc_hash_table->control->partitions[fc_partition].count;
	}
	else
	{
		Assert(false);
	}
}

/*
 * 如有必要，扩大哈希表至所请求的桶数。请求的大小必须是之前观察到的一些大小的两倍。
 *
 * 必须在不持有任何分区锁的情况下调用。
 */
static void fc_resize(dshash_table *fc_hash_table, size_t fc_new_size_log2)
{
	dsa_pointer fc_old_buckets;
	dsa_pointer fc_new_buckets_shared;
	dsa_pointer *fc_new_buckets;
	size_t		fc_size;
	size_t		fc_new_size = ((size_t) 1) << fc_new_size_log2;
	size_t		fc_i;

	/*
	 * 获取所有锁定分区的锁。这是昂贵的，但我们
	 * 不应该需要多次执行此操作。
	 */
	for (fc_i = 0; fc_i < DSHASH_NUM_PARTITIONS; ++fc_i)
	{
		Assert(!LWLockHeldByMe(PARTITION_LOCK(fc_hash_table, fc_i)));

		LWLockAcquire(PARTITION_LOCK(fc_hash_table, fc_i), LW_EXCLUSIVE);
		if (fc_i == 0 && fc_hash_table->control->size_log2 >= fc_new_size_log2)
		{
			/*
			 * 另一个后端已经增加了大小；我们可以避免
			 * 获取所有锁并提前返回。
			 */
			LWLockRelease(PARTITION_LOCK(fc_hash_table, 0));
			return;
		}
	}

	Assert(fc_new_size_log2 == fc_hash_table->control->size_log2 + 1);

	/* 为新表分配空间。 */
	fc_new_buckets_shared =
		dsa_allocate_extended(fc_hash_table->area,
							  sizeof(dsa_pointer) * fc_new_size,
							  DSA_ALLOC_HUGE | DSA_ALLOC_ZERO);
	fc_new_buckets = dsa_get_address(fc_hash_table->area, fc_new_buckets_shared);

	/*
	 * 我们已分配新的桶数组；现在剩下要做的就是
	 * 重新插入所有项，这相当于调整所有指针。
	 */
	fc_size = ((size_t) 1) << fc_hash_table->control->size_log2;
	for (fc_i = 0; fc_i < fc_size; ++fc_i)
	{
		dsa_pointer fc_item_pointer = fc_hash_table->buckets[fc_i];

		while (DsaPointerIsValid(fc_item_pointer))
		{
			dshash_table_item *fc_item;
			dsa_pointer fc_next_item_pointer;

			fc_item = dsa_get_address(fc_hash_table->area, fc_item_pointer);
			fc_next_item_pointer = fc_item->next;
			fc_insert_item_into_bucket(fc_hash_table, fc_item_pointer, fc_item,
									&fc_new_buckets[BUCKET_INDEX_FOR_HASH_AND_SIZE(fc_item->hash,
																				fc_new_size_log2)]);
			fc_item_pointer = fc_next_item_pointer;
		}
	}

	/* 交换哈希表并释放旧的哈希表。 */
	fc_old_buckets = fc_hash_table->control->buckets;
	fc_hash_table->control->buckets = fc_new_buckets_shared;
	fc_hash_table->control->size_log2 = fc_new_size_log2;
	fc_hash_table->buckets = fc_new_buckets;
	dsa_free(fc_hash_table->area, fc_old_buckets);

	/* 释放所有锁。 */
	for (fc_i = 0; fc_i < DSHASH_NUM_PARTITIONS; ++fc_i)
		LWLockRelease(PARTITION_LOCK(fc_hash_table, fc_i));
}

/*
 * 确保我们的后端局部桶指针是最新的。调用者必须锁定一个锁定分区，这将防止resize()并发执行。
 */
static inline void fc_ensure_valid_bucket_pointers(dshash_table *fc_hash_table)
{
	if (fc_hash_table->size_log2 != fc_hash_table->control->size_log2)
	{
		fc_hash_table->buckets = dsa_get_address(fc_hash_table->area,
											  fc_hash_table->control->buckets);
		fc_hash_table->size_log2 = fc_hash_table->control->size_log2;
	}
}

/*
 * 针对锁定的桶使用提供的比较函数扫描匹配项。
 */
static inline dshash_table_item *
fc_find_in_bucket(dshash_table *fc_hash_table, const void *fc_key,
			   dsa_pointer fc_item_pointer)
{
	while (DsaPointerIsValid(fc_item_pointer))
	{
		dshash_table_item *fc_item;

		fc_item = dsa_get_address(fc_hash_table->area, fc_item_pointer);
		if (fc_equal_keys(fc_hash_table, fc_key, ENTRY_FROM_ITEM(fc_item)))
			return fc_item;
		fc_item_pointer = fc_item->next;
	}
	return NULL;
}

/*
 * 将已分配的项插入到桶中。
 */
static void fc_insert_item_into_bucket(dshash_table *fc_hash_table,
						dsa_pointer fc_item_pointer,
						dshash_table_item *fc_item,
						dsa_pointer *fc_bucket)
{
	Assert(fc_item == dsa_get_address(fc_hash_table->area, fc_item_pointer));

	fc_item->next = *fc_bucket;
	*fc_bucket = fc_item_pointer;
}

/*
 * 为给定键分配空间并将其插入到
 * 提供的桶中。
 */
static dshash_table_item *
fc_insert_into_bucket(dshash_table *fc_hash_table,
				   const void *fc_key,
				   dsa_pointer *fc_bucket)
{
	dsa_pointer fc_item_pointer;
	dshash_table_item *fc_item;

	fc_item_pointer = dsa_allocate(fc_hash_table->area,
								fc_hash_table->params.entry_size +
								MAXALIGN(sizeof(dshash_table_item)));
	fc_item = dsa_get_address(fc_hash_table->area, fc_item_pointer);
	memcpy(ENTRY_FROM_ITEM(fc_item), fc_key, fc_hash_table->params.key_size);
	fc_insert_item_into_bucket(fc_hash_table, fc_item_pointer, fc_item, fc_bucket);
	return fc_item;
}

/*
 * 在桶中搜索匹配的键并删除它。
 */
static bool fc_delete_key_from_bucket(dshash_table *fc_hash_table,
					   const void *fc_key,
					   dsa_pointer *fc_bucket_head)
{
	while (DsaPointerIsValid(*fc_bucket_head))
	{
		dshash_table_item *fc_item;

		fc_item = dsa_get_address(fc_hash_table->area, *fc_bucket_head);

		if (fc_equal_keys(fc_hash_table, fc_key, ENTRY_FROM_ITEM(fc_item)))
		{
			dsa_pointer fc_next;

			fc_next = fc_item->next;
			dsa_free(fc_hash_table->area, *fc_bucket_head);
			*fc_bucket_head = fc_next;

			return true;
		}
		fc_bucket_head = &fc_item->next;
	}
	return false;
}

/*
 * 从桶中删除指定项。
 */
static bool fc_delete_item_from_bucket(dshash_table *fc_hash_table,
						dshash_table_item *fc_item,
						dsa_pointer *fc_bucket_head)
{
	while (DsaPointerIsValid(*fc_bucket_head))
	{
		dshash_table_item *fc_bucket_item;

		fc_bucket_item = dsa_get_address(fc_hash_table->area, *fc_bucket_head);

		if (fc_bucket_item == fc_item)
		{
			dsa_pointer fc_next;

			fc_next = fc_item->next;
			dsa_free(fc_hash_table->area, *fc_bucket_head);
			*fc_bucket_head = fc_next;
			return true;
		}
		fc_bucket_head = &fc_bucket_item->next;
	}
	return false;
}

/*
 * 计算键的哈希值。
 */
static inline dshash_hash
fc_hash_key(dshash_table *fc_hash_table, const void *fc_key)
{
	return fc_hash_table->params.hash_function(fc_key,
											fc_hash_table->params.key_size,
											fc_hash_table->arg);
}

/*
 * 检查两个键是否相等。
 */
static inline bool fc_equal_keys(dshash_table *fc_hash_table, const void *fc_a, const void *fc_b)
{
	return fc_hash_table->params.compare_function(fc_a, fc_b,
											   fc_hash_table->params.key_size,
											   fc_hash_table->arg) == 0;
}
